import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.HashSet;
 

public class HashChain {
	//for use by client only.
	private int length; 
	private byte[] seed; 
	private byte[] signed; 
	//for use by bank. 
	private HashChain previousChain;
	private byte[] top;
	private byte[] lowestSeen;
	private int remaining;
	private static HashSet<String> used = new HashSet<String>();
	
	public static void main(String[] args){
		HashChain chain = new HashChain(14);
		HashChain bank = new HashChain(asByte(chain.getTop()), 14);
		if(bank.verifyPayment(2, chain.getCoin(13))!= null) System.out.println("yes");
		if(bank.verifyPayment(2, chain.getCoin(13))!= null) System.out.println(" no");
	}
	
	
	
	//for use by client:  
	public HashChain(int l){
		length = l; 
		seed = new byte[32];
		try {
			SecureRandom rn = SecureRandom.getInstance("SHA1PRNG");
			rn.nextBytes(seed);
			top = asByte(getCoin(l));
		} catch (NoSuchAlgorithmException e) {
			// TODO Auto-generated catch block
		}
	}
	
	//for use  by bank: 
	public HashChain(byte[] t, int l){
		lowestSeen = null;
		top = t;
		length = l;
		remaining = l;
	}
	
	public int getRemaining(){ return remaining;}
	
	public String verifyPayment(int amt, String hash){
		if (amt>remaining) {
			return null;
		}
		if(used.contains(hash)) {
			return null;
		}
		byte[] coin = asByte(hash);
		used.add(asHex(coin));
		MessageDigest h;
		try {
			h = MessageDigest.getInstance("SHA-256");
			for(int i=1; i<amt; i++){
				coin = h.digest(coin);
				if (!used.add(asHex(coin))) {
					return null;
				}
			}
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}
		if((lowestSeen==null) || (asHex(lowestSeen).equals(asHex(coin)))){
			lowestSeen = asByte(hash);
			remaining-=amt;
			return getTop();
		}
		return null;
	}
	
	public void setPrevious(HashChain p){
		previousChain = p;
	}
	
	public HashChain getPrevious(HashChain p){
		return previousChain;
	}
	
	public void putSignature(byte[] sig){signed = sig;}
	
	//returns the n'th hash FROM THE BOTTOM in the hash chain. 
	public String getCoin(int n){
		byte[] coin = seed;
		try {
			MessageDigest hash = MessageDigest.getInstance("SHA-256");
			for(; n>=1; n--)
				coin = hash.digest(coin);
			return asHex(coin);
		} catch (NoSuchAlgorithmException e) {		
			return null;		
		}
	}
	//Removes n coins from the top of the chain. 
	public String popCoins(int n){
		String coin = getCoin(length-(n-1));
		length-=n;
		return coin;
	}
	
	public String getTop(){return asHex(top);}
	public void setTop(int l){length = l;}
	public int getLength(){return length;}
	
	public String getSig(){return asHex(signed);}
	//converts this to hex for the niceness of looking at it. 
    public static String asHex(byte[] coin)
    {
        String s = new BigInteger(1, coin).toString(16);
        return (s.length() % 2 == 0) ? s : "0" + s;
    }
    public static byte[] asByte(String s) {
        int len = s.length();
        byte[] data = new byte[len / 2];
        for (int i = 0; i < len; i += 2) {
            data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
                                 + Character.digit(s.charAt(i+1), 16));
        }
        return data;
    }

    
	
}